package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/largest-element-in-an-array-after-merge-operations/'>合并后数组中的最大元素(Largest Element in an Array after Merge Operations)</a>
 * <p>给你一个下标从 0 开始、由正整数组成的数组 nums 。</p>
 * <p>
 * 你可以在数组上执行下述操作 任意 次：
 *     <ul>
 *         <li>选中一个同时满足 0 <= i < nums.length - 1 和 nums[i] <= nums[i + 1] 的整数 i 。将元素 nums[i + 1] 替换为 nums[i] + nums[i + 1] ，并从数组中删除元素 nums[i] 。</li>
 *     </ul>
 * </p>
 * <p>返回你可以从最终数组中获得的 最大 元素的值。</p>
 *
 * <p>
 * <b>示例</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [2,3,7,9,3]
 *      输出：21
 *      解释：我们可以在数组上执行下述操作：
 *          - 选中 i = 0 ，得到数组 nums = [5,7,9,3] 。
 *          - 选中 i = 1 ，得到数组 nums = [5,16,3] 。
 *          - 选中 i = 0 ，得到数组 nums = [21,3] 。
 *          最终数组中的最大元素是 21 。可以证明我们无法获得更大的元素。
 *
 * 示例 2：
 *      输入：nums = [5,3,3]
 *      输出：11
 *      解释：我们可以在数组上执行下述操作：
 *          - 选中 i = 1 ，得到数组 nums = [5,6] 。
 *          - 选中 i = 0 ，得到数组 nums = [11] 。
 *          最终数组中只有一个元素，即 11 。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>1 <= nums.length <= 10^5</li>
 *      <li>1 <= nums[i] <= 10^6</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/3/14 9:17
 */
public class LC2789LargestElementInArrayAfterMergeOperations_M {

    static class Solution {
        public long maxArrayValue(int[] nums) {
            long maxVal = nums[nums.length - 1];
            for (int i = nums.length - 2; i >= 0; --i) {
                maxVal = nums[i] <= maxVal ? maxVal + nums[i] : nums[i];
            }
            return maxVal;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxArrayValue(new int[]{2, 3, 7, 9, 3}));
        System.out.println(solution.maxArrayValue(new int[]{5, 3, 3}));
        System.out.println(solution.maxArrayValue(new int[]{1, 4, 9, 7, 8, 5, 3}));
    }
}
